/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * copyTree(TreeNode *root, int diff) {
      if (root == NULL) {
        return NULL;
      }
      TreeNode* copyRoot = new TreeNode(root->val + diff);
      copyRoot->left = copyTree(root->left, diff);
      copyRoot->right = copyTree(root->right, diff);

      return copyRoot;
    }

    vector<TreeNode *> generateTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<TreeNode *> > trees(n + 1);

        trees[0].push_back(NULL);

        if (n == 0) {
          return trees[0];
        }

        trees[1].push_back(new TreeNode(1));
        for (int i = 2; i <= n; ++i) {
          for (int j = 1; j <= i; ++j) {

            for (int l = 0; l < trees[j - 1].size(); ++l) {
              for (int r = 0; r < trees[i - j].size(); ++r) {
                TreeNode* root = new TreeNode(j);
                root->left = copyTree(trees[j - 1][l], 0);
                root->right = copyTree(trees[i - j][r], j);
                trees[i].push_back(root);
              }
            }
          }
        }
        return trees[n];
    }
};
